/*
<a> (j == 0 or i == m or B[j-1] <= A[i]) and
    (i == 0 or j = n or A[i-1] <= B[j])
    Means i is perfect, we can stop searching.

<b> j > 0 and i < m and B[j - 1] > A[i]
    Means i is too small, we must increase it.

<c> i > 0 and j < n and A[i - 1] > B[j]
    Means i is too big, we must decrease it.
	

	
max(A[i-1], B[j-1]) (when m + n is odd)
or (max(A[i-1], B[j-1]) + min(A[i], B[j]))/2 (when m + n is even)
*/

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int i, j, m, n, i_min, i_max;
        vector<int>& A = nums1.size() > nums2.size() ? nums2 : nums1;
        vector<int>& B = nums1.size() <= nums2.size() ? nums2 : nums1;
        m = A.size();
        n = B.size();
        i_min = 0;
        i_max = A.size();
        while(i_min <= i_max){
            i = (i_min+i_max)/2;
            j = (m+n+1)/2-i;
            if(i < m && B[j-1] > A[i]){
                //TODO:increase i
                i_min = i+1;
            }else if(i > 0 && A[i-1] > B[j]){
                //TODO:decrease i
                i_max = i-1;
            }else{
                //(j == 0 || i == m || B[j-1] <= A[i]) && 
                //(i == 0 || j == n || A[i-1] <= B[j])
                //max(A[i-1], B[j-1]) (when m + n is odd)
                //or (max(A[i-1], B[j-1]) + min(A[i], B[j]))/2 (when m + n is even)
                //TODO:i is ok, judge answer odd or even
                int max_of_left, min_of_right;
                if(i == 0)
                    max_of_left = B[j-1];
                else if(j == 0)
                    max_of_left = A[i-1];
                else
                    max_of_left = max(A[i-1], B[j-1]);
                
                if((m+n)%2 == 1) return max_of_left;
                
                if(i == m)
                    min_of_right = B[j];
                else if(j == n)
                    min_of_right = A[i];
                else
                    min_of_right = min(A[i], B[j]);
                
                return (max_of_left+min_of_right)/2.0;
            }
        }
    }
};